#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        using LL = long long;
        LL res = 0;
        int cnt = 0, n = nums.size();
        vector<int> hash(min(n + 1, modulo));
        hash[0] = 1;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] % modulo == k)
                ++cnt;
            if (cnt >= k)
                res += hash[(cnt - k) % modulo];
            hash[cnt % modulo]++;
        }
        return res;
    }
};